package org.example;

import java.util.*;

/**
 * @author HAN Bing
 * @date 2021/6/25
 */
public class AppTest07 {

    // 888. Fair Candy Swap
    class Solution {
        // 0 1 2 3
        public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
            int sumA = Arrays.stream(aliceSizes).sum();
            int sumB = Arrays.stream(bobSizes).sum();
            int delta = (sumA - sumB) / 2;
            Set<Integer> aSet = new HashSet<>();
            for (int num : aliceSizes) {
                aSet.add(num);
            }

            for (int y : bobSizes) {
                int x = y + delta;
                if (aSet.contains(x)) {
                    return new int[]{x, y};
                }
            }
            return null;
        }
    }

    // 896. Monotonic Array
    class Solution {
        // 0 1 2 3
        public boolean isMonotonic(int[] nums) {
            boolean inc = true, dec = true;
            for (int i = 0; i < nums.length - 1; ++i) {
                if (nums[i] > nums[i + 1]) {
                    inc = false;
                }
                if (nums[i] < nums[i + 1]) {
                    dec = false;
                }
            }
            return inc || dec;
        }
    }

    // 897. Increasing Order Search Tree 0 1 2 3
    class Solution {
        TreeNode cur;
        public TreeNode increasingBST(TreeNode root) {
            TreeNode sentinel = new TreeNode(-1);
            cur = sentinel;
            inorder(root);
            return sentinel.right;
        }

        public void inorder(TreeNode node) {
            if (node == null) return;
            inorder(node.left);
            cur.right = node;
            node.left = null;
            cur = node;
            inorder(node.right);
        }
    }

    // 905. Sort Array By Parity I
        public int[] sortArrayByParity(int[] A) {
            int i = 0, j = A.length - 1;
            while (i < j) {
                if (A[i] % 2 == 1 && A[j] % 2 == 0) {
                    int tmp = A[i];
                    A[i] = A[j];
                    A[j] = tmp;
                }
                if (A[i] % 2 == 0) {
                    i++;
                }
                if (A[j] % 2 == 1) {
                    j--;
                }
            }
            return A;
        }
    }

    // 914. X of a Kind in a Deck of Cards 0 1 2 3
    class Solution {
        public boolean hasGroupsSizeX(int[] deck) {
            int[] count = new int[10000];
            for (int c: deck) {
                count[c]++;
            }

            int g = -1;
            for (int i = 0; i < 10000; ++i) {
                if (count[i] > 0) {
                    if (g == -1) {
                        g = count[i];
                    } else {
                        g = gcd(g, count[i]);
                    }
                }
            }
            return g >= 2;
        }

        public int gcd(int x, int y) {
            return x == 0 ? y : gcd(y % x, x);
        }
    }

    // 917. Reverse Only Letters 0 1 2 3
    class Solution {
        public String reverseOnlyLetters(String S) {
            Deque<Character> letters = new ArrayDeque<>();
            for (char c: S.toCharArray())
                if (Character.isLetter(c))
                    letters.push(c);

            StringBuilder ans = new StringBuilder();
            for (char c: S.toCharArray()) {
                if (Character.isLetter(c))
                    ans.append(letters.pop());
                else
                    ans.append(c);
            }
            return ans.toString();
        }
    }

    // 922. Sort Array By Parity II 0 1 2 3
    class Solution {
        public int[] sortArrayByParityII(int[] A) {
            int j = 1;
            for (int i = 0; i < A.length; i += 2) {
                if (A[i] % 2 == 1) {
                    while (A[j] % 2 == 1) {
                        j += 2;
                    }
                    swap(A, i, j);
                }
            }
            return A;
        }

        public void swap(int[] A, int i, int j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }

    // 938. Range Sum of BST 0 1 2 3
    class Solution {
        int ans = 0;
        public int rangeSumBST(TreeNode root, int L, int R) {
            dfs(root, L, R);
            return ans;
        }

        public void dfs(TreeNode node, int L, int R) {
            if (node != null) {
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                dfs(node.left, L, R);
                dfs(node.right, L, R);
            }
        }
    }

    // 941. Valid Mountain Array 0 1 2 3
    class Solution {
        public boolean validMountainArray(int[] A) {
            int N = A.length, i = 0;

            // walk up
            while (i != N - 1 && A[i] < A[i+1])
                i++;

            // peak can't be first or last
            if (i == 0 || i == N-1)
                return false;

            // walk down
            while (i != N - 1 && A[i] > A[i+1])
                i++;

            return i == N-1;
        }
    }

    // 942. DI String Match (N N) 0 1
    class Solution {
        public int[] diStringMatch(String S) {
            int N = S.length();
            int lo = 0, hi = N;
            int[] ans = new int[N + 1];
            for (int i = 0; i < N; ++i) {
                if (S.charAt(i) == 'I')
                    ans[i] = lo++;
                else
                    ans[i] = hi--;
            }
            ans[N] = lo;
            return ans;
        }
    }
    // 2 3
    class Solution {
        public int[] diStringMatch(String S) {
            int N = S.length();
            int lo = 0, hi = N;
            List<Integer> ans = new ArrayList<>();
            for (char c : S.toCharArray()) {
                if (c == 'D')
                    ans.add(hi--);
                else
                    ans.add(lo++);
            }
            ans.add(lo);
            return ans.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    // 953. Verifying an Alien Dictionary 0 1 2 3
    class Solution {
        public boolean isAlienSorted(String[] words, String order) {
            int[] orderMap = new int[order.length()];
            for (int i = 0; i < order.length(); i++){
                orderMap[order.charAt(i) - 'a'] = i;
            }

            for (int i = 0; i < words.length - 1; i++) {

                for (int j = 0; j < words[i].length(); j++) {
                    // If we do not find a mismatch letter between words[i] and words[i + 1],
                    // we need to examine the case when words are like ("apple", "app").
                    if (j >= words[i + 1].length()) return false;

                    if (words[i].charAt(j) != words[i + 1].charAt(j)) {
                        int currentWordChar = words[i].charAt(j) - 'a';
                        int nextWordChar = words[i + 1].charAt(j) - 'a';
                        if (orderMap[currentWordChar] > orderMap[nextWordChar]) return false;
                            // if we find the first different letter and they are sorted,
                            // then there's no need to check remaining letters
                        else break;
                    }
                }
            }

            return true;
        }
    }

    // 961. N-Repeated Element in Size (N N) 2N Array 0 1 2 3
    class Solution {
        public int repeatedNTimes(int[] A) {
            Set<Integer> ansSet = new HashSet<>();
            for (int x : A) {
                if (!ansSet.add(x)) {
                    return x;
                }
            }
            throw null;
        }
    }

    // 965. Univalued Binary Tree (N N) 0 1
    class Solution {
        List<Integer> vals;
        public boolean isUnivalTree(TreeNode root) {
            vals = new ArrayList();
            dfs(root);
            for (int v: vals)
                if (v != vals.get(0))
                    return false;
            return true;
        }

        public void dfs(TreeNode node) {
            if (node != null) {
                vals.add(node.val);
                dfs(node.left);
                dfs(node.right);
            }
        }
    }
    // 2 3
    class Solution {
        List<Integer> vals = new ArrayList();
        public boolean isUnivalTree(TreeNode root) {
            dfs(root);
            for (int v: vals)
                if (v != vals.get(0))
                    return false;
            return true;
        }

        public void dfs(TreeNode node) {
            if (node != null) {
                vals.add(node.val);
                dfs(node.left);
                dfs(node.right);
            }
        }
    }

    // 976. Largest Perimeter Triangle (NlogN, 1) 0 1 2 3
    class Solution {
        public int largestPerimeter(int[] A) {
            Arrays.sort(A);
            for (int i = A.length - 1; i >= 2; --i) {
                if (A[i - 2] + A[i - 1] > A[i]) {
                    return A[i - 2] + A[i - 1] + A[i];
                }
            }
            return 0;
        }
    }

    // 977. Squares of a Sorted Array (N N) 0 1
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int n = nums.length;
            int[] ans = new int[n];
            for (int i = 0, j = n - 1, pos = n - 1; i <= j; pos--) {
                int iSquare = nums[i] * nums[i], jSquare = nums[j] * nums[j];
                if (iSquare > jSquare) {
                    ans[pos] = iSquare;
                    ++i;
                } else {
                    ans[pos] = jSquare;
                    --j;
                }
            }
            return ans;
        }
    }
    // 2
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int[] ans = new int[nums.length];
            for (int i = 0, j = nums.length - 1, pos = j; i <= j; pos--) {
                int iSquare = nums[i] * nums[i], jSquare = nums[j] * nums[j];
                if (iSquare > jSquare) {
                    ans[pos] = iSquare;
                    ++i;
                } else {
                    ans[pos] = jSquare;
                    --j;
                }
            }
            return ans;
        }
    }
    // 3
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int left = 0, right = nums.length - 1, ansPos = nums.length - 1;
            int[] ans = new int[nums.length];
            while (left <= right){
                int leftSquare = nums[left] * nums[left], rightSquare = nums[right] * nums[right];
                if (leftSquare > rightSquare) {
                    ans[ansPos] = leftSquare;
                    ++left;
                } else {
                    ans[ansPos] = rightSquare;
                    --right;
                }
                ansPos--;
            }
            return ans;
        }
    }

    // 985. Sum of Even Numbers After Queries (N+Q Q) 0 1 2 3
    class Solution {
        public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
            int S = 0;
            for (int x: A)
                if (x % 2 == 0)
                    S += x;

            int[] ans = new int[queries.length];

            for (int i = 0; i < queries.length; ++i) {
                int val = queries[i][0], index = queries[i][1];
                if (A[index] % 2 == 0) S -= A[index];
                A[index] += val;
                if (A[index] % 2 == 0) S += A[index];
                ans[i] = S;
            }

            return ans;
        }
    }

    // 989. Add to Array-Form of Integer (max(N, lg K), max(N, lg K) 0 1
    class Solution {
        public List<Integer> addToArrayForm(int[] A, int K) {
            int N = A.length;
            int cur = K;
            List<Integer> ans = new ArrayList();

            int i = N;
            while (--i >= 0 || cur > 0) {
                if (i >= 0)
                    cur += A[i];
                ans.add(cur % 10);
                cur /= 10;
            }

            Collections.reverse(ans);
            return ans;
        }
        // 1
        public List<Integer> addToArrayForm(int[] A, int K) {
            int i = A.length;
            List<Integer> ans = new ArrayList();
            while (--i >= 0 || K > 0) {
                if (i >= 0) {
                    K += A[i];
                }
                ans.add(K % 10);
                K /= 10;
            }

            Collections.reverse(ans);
            return ans;
        }
        // 2 3
        public List<Integer> addToArrayForm(int[] A, int K) {
            int i = A.length - 1;
            List<Integer> ans = new ArrayList<>();
            while (i >= 0 || K > 0) {
                if (i >= 0) {
                    K += A[i];
                }
                ans.add(K % 10);
                K /= 10;
                i--;
            }
            Collections.reverse(ans);
            return ans;
        }
    }

    // 1022. Sum of Root To Leaf Binary Numbers （N H） 0 1 2
    class Solution {
        int rootToLeaf = 0;

        public int sumRootToLeaf(TreeNode root) {
            preorder(root, 0);
            return rootToLeaf;
        }

        public void preorder(TreeNode r, int currNumber) {
            if (r != null) {
                currNumber = (currNumber << 1) | r.val;
                // if it's a leaf, update root-to-leaf sum
                if (r.left == null && r.right == null) {
                    rootToLeaf += currNumber;
                }
                preorder(r.left, currNumber);
                preorder(r.right, currNumber);
            }
        }
    }

    // 1089. Duplicate Zeros （N 1） 0 1
    class Solution {
        public void duplicateZeros(int[] arr) {
            int possibleDups = 0, right = arr.length - 1;

            // Find the number of zeros to be duplicated
            // Stopping when left points beyond the last element in the original array
            // which would be part of the modified array
            for (int left = 0; left <= right - possibleDups; left++) {

                // Count the zeros
                if (arr[left] == 0) {

                    // Edge case: This zero can't be duplicated. We have no more space,
                    // as left is pointing to the last element which could be included
                    if (left == right - possibleDups) {
                        // For this zero we just copy it without duplication.
                        arr[right] = 0;
                        right -= 1;
                        break;
                    }
                    possibleDups++;
                }
            }

            // Start backwards from the last element which would be part of new array.
            // Copy zero twice, and non zero once.
            for (int i = right - possibleDups; i >= 0; i--, right--) {
                if (arr[i] == 0) {
                    arr[right] = 0;
                    right--;
                    arr[right] = 0;
                } else {
                    arr[right] = arr[i];
                }
            }
        }
    }

    // 1217. Minimum Cost to Move Chips to The Same Position 0
    class Solution {
        public int minCostToMoveChips(int[] position) {
            int even_cnt = 0, odd_cnt = 0;
            for (int i : position) {
                if (i % 2 == 0) {
                    even_cnt++;
                } else {
                    odd_cnt++;
                }
            }
            return Math.min(odd_cnt, even_cnt);
        }
    }

}
